#include <algorithm>
#include <cstdint>
#include <iostream>
#include <istream>
#include <vector>
using ll = int64_t;

ll t;

int main(){
    std::iostream::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin>>t;
    std::vector<ll> a;
    std::vector<bool> dp;
    while(t--){
        ll n;
        std::cin>>n;
        ll ans=n;
        a.clear();
        dp.clear();
        a.resize(n+1);
        

        for(ll i=1;i<=n;i++){
            std::cin>>a[i];
        }
        std::sort(a.begin()+1,a.begin()+1+n);
        dp.resize(a[n]+1);
        dp[0]=true;
        for(ll i=1;i<=n;i++){
            if(dp[a[i]]){
                ans--;
                continue;
            }
            for(ll j=a[i];j<=a[n];j++){
                dp[j]=dp[j]|dp[j-a[i]];
            }
        }
        std::cout<<ans<<"\n";
    }
}